This invention relates to a system for parallel processing of multiple operands using residue arithmetic notation and for decoding the results to provide a normal number, such as a decimal number.
At present most digital computers are based on a weighted number system such as binary which is implemented via Boolean techniques. The speed of calculations in a weighted number system is limited by the propagation of a carry. This and the fact that Boolean techniques require that a signal be detected and restimulated at each level of logic severely restricts the type of signals and phenomena which can be used.
The quest for speed has prompted the investigation of alternate number systems such as the residue system where addition, multiplication, and integer polynominals transforms can be accomplished in parallel without a carry. The residue system was first applied to computers in 1956 by M. Valach and A. Svobada in Czechoslovakia and independently by H. L. Garner in the United States.
One of the earliest papers is by H. L. Garner, et. al., "The Residue Number System," IRE Trans. Electronic Computers, Vol. EC-8, pp. 140-147, June 1959. A survey of the field is given in a book by N. S. Szabo and R. I. Tanaka, Residue Arithmetic and Its Application to Computer Technology, N.Y., McGraw-Hill, 1967.
Recent work has been devoted towards trying to cast residue arithmetic in to a form amenable to Boolean techniques so that conventional logic circuits can be used. Unfortunately, the potential benefits of this approach do not justify the additional complexity in hardware. There exists non-Boolean approaches which can bypass some of these constraints. The characteristics of the residue system can be mimiced by various physical phenomena. This is discussed in an article by the applicant, "The Implementation of a Residue Arithmetic Unit via Optical and Other Physical Phenomena," International Optical Computing Conference, 1975, Digest of Papers, N.Y., IEEE, Apr. 1975.
Some of the early work by Svobada and Valach involving electromechanical relays can also in retrospect be viewed as non-Boolean. A description can be found in "Computer Progress in Czechoslovakia II, The Numerical Systems of Residue Classes" in Digital Information Processor, Walter Hoffmann, ed., John Wiley & Sons, Inc., N.Y. 1962. More detail is given in A. Svobada and M. Valach, Operatorove obvody (Operational Circuits), Straje na Gpracovani Infomcici, Sbornik III, Nakl, CSAV, Praka, 1955. Translation can be found: Information Processing Machines, National Technical Information Service, reference number AD757160. These references show the use of mathematical transformations, in pictorial form.
In spite of all these efforts the residue has remained a mere academic curiosity because the difficulties in converting back from such a system has offset most of the potential advantages. What has been lacking is an effective means to perform this conversion and the incorporation of such a mechanism into a complete processing system. Also lacking has been the ability to process in parallel, multiplexing and pipelining.